/*
 * com.future CO.,ltd.
 */

package com.future;

import java.lang.*;
import java.util.*;

/**
 * Description: ��ˢ���9
 * ����һ����ά�������� envelopes ������ envelopes[i] = [wi, hi] ����ʾ�� i ���ŷ�Ŀ�Ⱥ͸߶ȡ�
 * <p>
 * ����һ���ŷ�Ŀ�Ⱥ͸߶ȶ�������ŷ���ʱ������ŷ�Ϳ��ԷŽ���һ���ŷ����ͬ����˹����һ����
 * <p>
 * ����� ������ж��ٸ� �ŷ������һ�顰����˹���ޡ��ŷ⣨�����԰�һ���ŷ�ŵ���һ���ŷ����棩��
 * <p>
 * ע�⣺��������ת�ŷ⡣
 * ʾ�� 1��
 * <p>
 * ���룺envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * �����3
 * ���ͣ�����ŷ�ĸ���Ϊ 3, ���Ϊ: [2,3] => [5,4] => [6,7]��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/russian-doll-envelopes
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/21:20:48
 */
public class Solution_354 {

    public static void main(String[] args) {
        int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
        envelopes = new int[][]{{1, 5}, {1, 3}, {1, 2}, {5, 6}, {5, 4}, {7, 6}, {7, 2}};
        System.out.println(maxEnvelopes(envelopes));
        System.out.println(maxEnvelopes_v2(envelopes));
    }

    /**
     * �Ż��汾
     * 1����߷ŵ�һ����������
     * 2���������򣨿��С���󣬿�һ�����߶ȴӴ�С��
     * 3��������ȡ�����ź���������ĸ߶ȣ��ŵ�����arr
     * 4����ôarr������������еĸ������Ǵ�****
     *
     * @param envelopes
     * @return
     */
    public static int maxEnvelopes_v2(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        if (envelopes.length == 1) {
            return 1;
        }
        int N = envelopes.length;
        MyObj[] objs = new MyObj[N];
        for (int i = 0; i < N; i++) {
            objs[i] = new MyObj(envelopes[i][0], envelopes[i][1]);
        }
        Arrays.sort(objs, new MyComparator());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = objs[i].height;
        }
        int[] end = new int[N];
        end[0] = arr[0];
        int R = 0;
        /**
         * ������������ɲο�
         * 300. �����������
         */
        for (int i = 1; i < N; i++) {
            int l = 0;
            int r = R;
            while (l <= r) {
                int m = l + ((r - l) >> 1);
                if (end[m] < arr[i]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            end[l] = arr[i];
            R = Math.max(R, l);
        }
        return R + 1;
    }

    /**
     * �����汾
     * ˼·��
     * 1����߷ŵ�һ����������
     * 2���������򣨿��С���󣬿�һ�����߶ȴӴ�С��
     * 3��������ȡ�����ź���������ĸ߶ȣ��ŵ�����arr
     * 4����ôarr������������еĸ������Ǵ�****
     *
     * @param envelopes
     * @return
     */
    public static int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }
        if (envelopes.length == 1) {
            return 1;
        }
        int N = envelopes.length;
        MyObj[] objs = new MyObj[N];
        for (int i = 0; i < N; i++) {
            objs[i] = new MyObj(envelopes[i][0], envelopes[i][1]);
        }
        Arrays.sort(objs, new MyComparator());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = objs[i].height;
        }
        int[] dp = new int[N];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < N; i++) {
            int ans = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    ans = Math.max(ans, dp[j] + 1);
                }
            }
            max = Math.max(max, ans);
            dp[i] = ans;
        }
        return max;
    }

    private static class MyObj {
        public int with;

        public int height;

        public MyObj(int witth, int height) {
            this.with = witth;
            this.height = height;
        }
    }

    private static class MyComparator implements Comparator<MyObj> {

        /**
         * ��ȴ�С���󣬿��һ�����߶ȴӴ�С
         *
         * @param o1
         * @param o2
         * @return
         */
        @Override
        public int compare(MyObj o1, MyObj o2) {
            return o1.with != o2.with ? o1.with - o2.with : o2.height - o1.height;
        }

    }
}
